<?php
/**
 * 难度：简单
 * 题目链接 https://leetcode.cn/problems/majority-element/description/
 */

class Solution {

    /**
     * @param int[] $nums
     * @return int
     */
    public static function majorityElement($nums): int 
    {
        $max_count = 1;
        $max = $nums[0];
        $map[$nums[0]] = 1;

        for ($i=1; $i < count($nums); $i++) { 
            if (isset($map[$nums[$i]])) {
                $map[$nums[$i]] += 1;
            } else {
                $map[$nums[$i]] = 1;
            }
            if ($max_count < $map[$nums[$i]]) {
                $max_count = $map[$nums[$i]];
                $max = $nums[$i];
                // 当最大的数量已经大于一半了 就一定是最多的 不用继续循环比较了
                if ($max_count >= count($nums)/2) {
                    break;
                }
            }
            
            // echo "i=$i num={$nums[$i]} max=$max max_count=$max_count" . PHP_EOL;
        }
        
        return $max;
    }
}

$test = [
    [[3,2,3]],
    [[2,2,1,1,1,2,2]],
];
$result = [
    3,
    2,
];

foreach ($test as $key => $value) {
    $r = Solution::majorityElement($value[0]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    echo $r . PHP_EOL;
}